Zkouška Tancer 22. 1. 2025

1. Definujte střední hodnotu náhodné veličiny. Určete střední hodnotu čísla, co padne na spravedlivé šestistěnné kostce. (Může padnout 1, 2, 3, 4, 5 nebo 6.)

2. [Nějaký příklad s principem inkluze a exkluze co jsem si bohužel nevyfotil, sorry]

3. Nechť $G=(V,E)$ je orientovaný graf. Na $V$ definujme relaci $\approx$ tak, že pro $u,v\in V$ máme $u\approx v$, právě když v $G$ existuje orientovaná cesta z $u$ do $v$ a také existuje orientovaná cesta z $v$ do $u$. (Orientovaný sled s jedním vrcholem a žádnou hranou též považujeme za orientovanou cestu.)
   (a) Dokažte, že $\approx$ je ekvivalence na $V$.
   (b) Nakreslete slabě souvislý orientovaný graf s 5 vrcholy takový, že $\approx$ má 3 třídy ekvivalence. (Třídy vyznačte, ale nemusíte ověřovat slabou souvislost, ani že jste třídy určili korektně.)

4. Formulujte a dokažte tvrzení/lemma o trhání listů. (Hint pro znění: Přidávání nebo odebírání listů z grafu zachovává jistou vlastnost, ale formulujte to pořádně)